package DataStrucures.graphTheory;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.LinkedList;

public class BreadthFirstSearch {

    public static void main(String[] args) {
        int n=5;
        String vertex[]={"A","B","C","D","E"};
        BreadthFirstSearch graph=new BreadthFirstSearch(n);
        for (String VertexValue:vertex) {
            graph.insertVertex(VertexValue);
        }
        graph.insertEdge(0,1,1);
        graph.insertEdge(0,2,1);
        graph.insertEdge(1,2,1);
        graph.insertEdge(1,3,1);
        graph.insertEdge(1,4,1);
        graph.showGraph();
        graph.bfs();

    }
    private ArrayList<String> vertexList;
    private int[][] edges;
    private int numOfEdges;
    private boolean[] isVisited;
    public BreadthFirstSearch( int n) {
        isVisited=new boolean[n];
        edges=new int[n][n];
        vertexList =new ArrayList<>(n);
        numOfEdges=0;
//        for (int i = 0; i < n; i++) {
//            isVisited[i]=false;
//        }
    }
   private void bfs(boolean[] isVisited,int i){
        int u;
        int w;
       LinkedList queue=new LinkedList();
       System.out.print(getValueByIndex(i)+"->");
       isVisited[i]=true;
       queue.addLast(i);
       while(!queue.isEmpty()){
           u=(Integer)queue.removeFirst();
           w=getFirstNeighbor(u);
           while (w!=-1){
               if(!isVisited[w]){
                   System.out.print(getValueByIndex(w)+"->");
                   isVisited[w]=true;
                   queue.addLast(w);
               }
               w=getNextNeighbor(u,w);
           }


       }
   }
   public void bfs(){
       for (int i = 0; i < getNumOfVertex(); i++) {
           if(!isVisited[i]){
               bfs(isVisited,i);
           }
       }
   }


    public int getNextNeighbor(int v1,int v2){
        for (int i = v2+1; i < vertexList.size(); i++) {
            if(edges[v1][i]>0){
                return i;
            }
        }
        return -1;
    }
    public int getFirstNeighbor(int index){
        for (int i = 0; i < vertexList.size(); i++) {
            if(edges[index][i]>0){
                return i;
            }
        }
        return -1;
    }
    public int getNumOfVertex(){
        return vertexList.size();
    }
    public void showGraph(){
        for (int[] l:edges) {
            System.out.println(Arrays.toString(l));
        }
    }
    public int getNumOfEdges() {
        return numOfEdges;
    }
    public String getValueByIndex(int i){
        return vertexList.get(i);
    }
    public int getWeight(int v1,int v2){
        return edges[v1][v2];
    }
    public void insertVertex(String vertex){
        vertexList.add(vertex);
    }
    public void insertEdge(int v1,int v2,int weight){
        edges[v1][v2]=weight;
        edges[v2][v1]=weight;
        numOfEdges++;
    }
}
